#pragma once

#include <iostream>
#include "dictionary.h"
#include "pairNode.h"


using namespace std;

template<class K, class E>
class sortedChain : public dictionary<K, E> {
	
public:
	sortedChain() { firstNode = NULL; dSize = 0; }
	~sortedChain() override;

	bool empty() const override { return dSize == 0; }
	int size() const override { return dSize; }

	pair<const K, E>* find(const K&) const override;
	void erase(const K&) override;
	void insert(const pair<const K, E>&) override;
	void output(ostream& out) const;

protected:
    /* pointer to the first node in chain */
	pairNode<K, E>* firstNode;
    /* number of elements in dictionary */
	int dSize;
};

template <class K, class E>
sortedChain<K, E>:: ~sortedChain()
{
    /* Destructor. Delete all nodes */
	while (firstNode != nullptr) {
		pairNode<K, E>* nextNode = firstNode->next;
		delete firstNode;
		firstNode = nextNode;
	}
}

template<class K, class E>
pair<const K, E>* sortedChain<K, E>::find(const K& theKey) const
{
	/* Return pointer to matching pair. */
    /* Return NULL if no matching pair. */
	pairNode<K, E>* curNode = firstNode;
    /* search for match with theKey*/
	while (curNode != nullptr && curNode->element.first != theKey) {
		curNode = curNode->next;
	}
    /* verify matching */
	if (curNode != nullptr && curNode->element.first == theKey)
        /* yes, found matching */
		return &curNode->element;

    // no match
	return nullptr;

}

template<class K, class E>
void sortedChain<K, E>::erase(const K& theKey)
{
	/* Delete the pair, if any, whose key equals theKey */
	pairNode<K, E>* p = firstNode,
		* tp = nullptr;

	/* Search for match with theKey */
	while (p != nullptr && p->element.first < theKey) {
		tp = p;
		p = p->next;
	}
	/* Verify match */
	if (p != nullptr && p->element.first == theKey) {
		/* remove p from the chain */
		if (tp == nullptr) firstNode = p->next;
		else tp->next = p->next;

		delete p;
		dSize--;
	}
}
/*
 * Insert thePair into the dictionary. Overwrite existing
 * pair, if any, with same key.
 * 
 */
template<class K, class E>
void sortedChain<K, E>::insert(const pair<const K, E>& thePair)
{
	pairNode<K, E>* p = firstNode, * tp = NULL;// tp trails p

	/* move tp so that thePair can be inserted after tp */
	while (p != nullptr && p->element.first < thePair.first) {
		tp = p;
		p = p->next;
	}
	/* check if there is a matching pair */
	if (p != nullptr && p->element.first == thePair.first) {
		/* replace old value */
		p->element.second = thePair.second;
		return;
	}
	/* no match, set up node for thePair */
	auto* newNode = new pairNode<K, E>(thePair, p);
	/* insert newNode just after tp*/
	if (tp == nullptr) firstNode = newNode;
	else tp->next = newNode;

	dSize++;

	
}

template<class K, class E>
void sortedChain<K, E>::output(ostream& out) const
{
	/* Insert the chain elements into the stream out. */
	for (pairNode<K, E>* curNode = firstNode;
		curNode != nullptr;
		curNode = curNode->next) {

		out << curNode->element.first << " "
			<< curNode->element.second << " ";
	}
}

// overwrite << 
template<class K, class E>
ostream& operator<<(ostream& out, const sortedChain<K, E>& x)
{
	x.output(out);
	return out;
}
